package Algorithms.greedy;

import java.util.*;

/*
 * @Author 罗俊
 * @date 2020/10/28 - 7:43 下午
 *
 */
public class Greedy {

    static final Set<String> allBroadcastSet;

    static final HashMap<String, Set<String>> broadcastMap;

    static {
        broadcastMap = new HashMap<>();

        HashSet<String> broadcast1 = new HashSet<>();


        broadcast1.add("北京");
        broadcast1.add("上海");
        broadcast1.add("天津");


        HashSet<String> broadcast2 = new HashSet<>();

        broadcast2.add("北京");
        broadcast2.add("广州");
        broadcast2.add("深圳");

        HashSet<String> broadcast3 = new HashSet<>();

        broadcast3.add("成都");
        broadcast3.add("上海");
        broadcast3.add("杭州");

        HashSet<String> broadcast4 = new HashSet<>();

        broadcast4.add("上海");
        broadcast4.add("天津");

        HashSet<String> broadcast5 = new HashSet<>();

        broadcast5.add("杭州");
        broadcast5.add("大连");

        broadcastMap.put("broadcast1", broadcast1);
        broadcastMap.put("broadcast2", broadcast2);
        broadcastMap.put("broadcast3", broadcast3);
        broadcastMap.put("broadcast4", broadcast4);
        broadcastMap.put("broadcast5", broadcast5);


        allBroadcastSet = new HashSet<>();

        broadcastMap.forEach((key, value) -> {
            allBroadcastSet.addAll(value);
        });
    }

    public static void main(String[] args) {


        System.out.println("所有的广播节点是：" + allBroadcastSet);

        List<String> selectedBroadNameList = new ArrayList<>();

        greedyNew(allBroadcastSet, broadcastMap, selectedBroadNameList);

        System.out.println("最终选择的广播是：" + selectedBroadNameList);

    }

    /**
     * 新版本（优化性能）
     * @param allBroadcastSet
     * @param broadcastMap
     * @param selectedBroadcastList
     */
    public static void greedyNew(Set<String> allBroadcastSet, HashMap<String, Set<String>> broadcastMap, List<String> selectedBroadcastList) {

        int repeatLocationCount = 0; //  当前 broadcast 与 allBroadcastSet 重叠的 location 数量，然后在所有 broadcast 中取最大值
        String maxRepeatKey = null; // 当前 broadcast 与  allBroadcastSet 重叠的 location 名字，然后在所有的 broadcast 中取重叠次数最多的哪个 broadcast 的名字


        for (Map.Entry<String, Set<String>> entry : broadcastMap.entrySet()) {


            // 将当前 broadcast 拷贝进 tempSet 中 方便使用
            HashSet<String> tempSet = new HashSet<>();
            tempSet.addAll(entry.getValue());
            // 将 tempSet 和 allBroadcastSet 求交集，交集继续赋值给 tempSet
            tempSet.retainAll(allBroadcastSet);

            // 如果当前 broadcast 与 allBroadcastSet 重叠的 location 比之前任何 broadcast 重叠的都要多，那就更新，最大重叠次数（由于寻找比当前重叠 location 更多的 broadcast）
            // 还更新 maxRepeatKey 更新最大重叠 allBroadcastSet 的 broadcast 的名字
            if (tempSet.size() > repeatLocationCount) {
                repeatLocationCount = tempSet.size();
                maxRepeatKey = entry.getKey();
            }

        }

        selectedBroadcastList.add(maxRepeatKey);

        System.out.println("本次选择的广播是:" + maxRepeatKey + "\t其包含的节点是（即将被移除）：" + broadcastMap.get(maxRepeatKey).toString());

        allBroadcastSet.removeAll(broadcastMap.get(maxRepeatKey));

        if (allBroadcastSet.size() > 0) {
            greedyNew(allBroadcastSet, broadcastMap, selectedBroadcastList);
        }

    }

    /**
     * 自己写的贪婪算法，有点复杂
     *
     * @param allBroadcastSet       所有 broadCast 需要覆盖的 location
     * @param broadcastMap          broadcast 与其 覆盖区域的映射
     * @param selectedBroadcastList 已经选择了的 broadcast（结果）
     */
    public static void greedy(Set<String> allBroadcastSet, HashMap<String, Set<String>> broadcastMap, List<String> selectedBroadcastList) {
        // 存储对应 单个broadcast 其节点覆盖 allBroadcastSet 中节点的个数
        Map<String, Integer> containLocationCountMap = new HashMap<>();

        int i = 0;
        for (Map.Entry<String, Set<String>> entry : broadcastMap.entrySet()) {

            Set<String> singleBroadcast = entry.getValue();

            String singleBroadcastName = entry.getKey();

            for (String location : singleBroadcast) {
                /**
                 * 如果，allBroadcastSet 包含当前 broadcast 中的某一位置节点，就在 containLocationCountMap 上对应 重叠节点个数 +1
                 * */
                if (allBroadcastSet.contains(location)) {

                    containLocationCountMap.putIfAbsent(singleBroadcastName, 0);

                    Integer singleBroadCastContainLocationCount = containLocationCountMap.get(singleBroadcastName);

                    containLocationCountMap.put(singleBroadcastName, singleBroadCastContainLocationCount + 1);

                }
            }

            i++;

        }

        // 从 containLocationCountMap 解析出重叠最多位置的节点，及其 broadCastName
        int maxRepeatCount = 0;
        String maxRepeatBroadcastName = null;
        for (Map.Entry<String, Integer> entry : containLocationCountMap.entrySet()) {

            if (entry.getValue() > maxRepeatCount) {
                maxRepeatCount = entry.getValue();
                maxRepeatBroadcastName = entry.getKey();
            }

        }

        Set<String> addedBroadcast = broadcastMap.get(maxRepeatBroadcastName);
        System.out.println("本次选择的广播是:" + maxRepeatBroadcastName + "\t其包含的节点是（即将被移除）：" + addedBroadcast.toString());

        // 从 allBroadcastSet 中删除已添加的 broadcast
        allBroadcastSet.removeAll(addedBroadcast);

        // 删除（这里不一定能加快）
        broadcastMap.remove(maxRepeatBroadcastName);

        selectedBroadcastList.add(maxRepeatBroadcastName);

        if (allBroadcastSet.size() > 0) {
            greedy(allBroadcastSet, broadcastMap, selectedBroadcastList);
        }
    }


}
